<html>
  <head>
	  <meta http-equiv="content-type" content="text/html; charset=utf-8" />
    <title>i5ting_ztree_toc:07</title>
		<link href="toc/style/github-bf51422f4bb36427d391e4b75a1daa083c2d840e.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/style/github2-d731afd4f624c99a4b19ad69f3083cd6d02b81d5.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/css/zTreeStyle/zTreeStyle.css" media="all" rel="stylesheet" type="text/css"/>
	  <style>
		pre {
		    counter-reset: line-numbering;
		    border: solid 1px #d9d9d9;
		    border-radius: 0;
		    background: #fff;
		    padding: 0;
		    line-height: 23px;
		    margin-bottom: 30px;
		    white-space: pre;
		    overflow-x: auto;
		    word-break: inherit;
		    word-wrap: inherit;
		}

		pre a::before {
		  content: counter(line-numbering);
		  counter-increment: line-numbering;
		  padding-right: 1em; /* space after numbers */
		  width: 25px;
		  text-align: right;
		  opacity: 0.7;
		  display: inline-block;
		  color: #aaa;
		  background: #eee;
		  margin-right: 16px;
		  padding: 2px 10px;
		  font-size: 13px;
		  -webkit-touch-callout: none;
		  -webkit-user-select: none;
		  -khtml-user-select: none;
		  -moz-user-select: none;
		  -ms-user-select: none;
		  user-select: none;
		}

		pre a:first-of-type::before {
		  padding-top: 10px;
		}

		pre a:last-of-type::before {
		  padding-bottom: 10px;
		}

		pre a:only-of-type::before {
		  padding: 10px;
		}

		.highlight { background-color: #ffffcc } /* RIGHT */
		</style>
  </head>
  <body>
	  <div>
				<div style='width:25%;'>
						<ul id="tree" class="ztree" style='width:100%'>

						</ul>
				</div>
        <div id='readme' style='width:70%;margin-left:20%;'>
          	<article class='markdown-body'>
            	<h1 id="07-">07. 重建二叉树</h1>
<p>难度：<strong>中等</strong></p>
<p>输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。</p>
<p>例如，给出</p>
<pre><code>前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]
</code></pre><p>返回如下的二叉树：</p>
<pre><code>    3

   / \\

9     20

    /  \\

15       7
</code></pre><p>限制：</p>
<p>0 &lt;= 节点个数 &lt;= 5000</p>
<p>来源：力扣（LeetCode）</p>
<p>链接：<a href="https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof">https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof</a></p>
<p>著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。</p>
<hr>
<p>解法1：递归构造树</p>
<p>前序遍历 preorder: 根 -- 左 -- 右   第一个肯定是根节点</p>
<p>中序遍历 inorder: 左 -- 根 -- 右</p>
<pre><code class="lang-Java">class Solution {
    HashMap&lt;Integer,Integer&gt; map = new HashMap&lt;&gt;();
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0){
            return null;
        }
        this.preorder = preorder;
        for(int i = 0;i &lt; inorder.length; i ++){
            map.put(inorder[i],i);
        }

        TreeNode node = startBuildTree(0 , 0 , preorder.length - 1);
        return node;
    }

    TreeNode startBuildTree(int root , int left, int right){
        if(left &gt; right){
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        int i = map.get(preorder[root]);
          // 寻找node的左节点:
        // 在前序遍历中的位置就是  根节点的下标 + 1（右边一个单位）
        // 在中序遍历中的位置就是： 1. 左边界不变，2. 右边界就是根节点的左边一个单位 in_root_index - 1
        node.left = startBuildTree(root + 1, left , i - 1);
        // 寻找node的右节点:
        // 在前序遍历中的位置就是  根节点的下标 + 左子树长度（ in_root_index - in_left_index） + 1
        // 在中序遍历中的位置就是： 1. 左边界在根节点的右边一个单位  in_root_index + 1, 2. 右边界不变
        node.right = startBuildTree(root + i - left + 1, i + 1, right);
        return node;
    }
}
</code></pre>

          	</article>
        </div>
		</div>
  </body>
</html>
<script type="text/javascript" src="toc/js/jquery-1.4.4.min.js"></script>
<script type="text/javascript" src="toc/js/jquery.ztree.all-3.5.min.js"></script>
<script type="text/javascript" src="toc/js/ztree_toc.js"></script>
<script type="text/javascript" src="toc_conf.js"></script>

<SCRIPT type="text/javascript" >
<!--
$(document).ready(function(){
    var css_conf = eval(markdown_panel_style);
    $('#readme').css(css_conf)
    
    var conf = eval(jquery_ztree_toc_opts);
		$('#tree').ztree_toc(conf);
});
//-->
</SCRIPT>